1 package joeq.Compiler.Analysis.IPSSA.Apps;
2
3 import java.util.Arrays;
4 import java.util.Collection;
5 import java.util.Collections;
6 import java.util.Comparator;
7 import java.util.HashMap;
8 import java.util.HashSet;
9 import java.util.Iterator;
10 import java.util.LinkedList;
11 import java.util.List;
12 import java.util.Map;
13 import java.util.Set;
14 import java.util.StringTokenizer;
15 import java.io.BufferedReader;
16 import java.io.FileReader;
17 import java.io.IOException;
18 import joeq.Class.PrimordialClassLoader;
19 import joeq.Class.jq_Class;
20 import joeq.Class.jq_Field;
21 import joeq.Class.jq_Method;
22 import joeq.Class.jq_Type;
23 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary;
24 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ReturnedNode;
25 import joeq.Compiler.Quad.CallGraph;
26 import joeq.Compiler.Quad.RootedCHACallGraph;
27 import joeq.Main.HostedVM;
28 import jwutil.collections.AppendIterator;
29 import jwutil.util.Assert;
30
31 class ClassHierarchy {
32 protected class ClassHieraryNode {
33 Set _children = new HashSet();
34 jq_Class _class = null;
35 ClassHieraryNode _parent = null;
36
37 ClassHieraryNode(jq_Class c){
38 this._class = c;
39 }
40 private void addChild(ClassHieraryNode n) {
41
42
43 _children.add(n);
44
45 }
46 public int getChildCount() {
47 return _children.size();
48 }
49 public Iterator getChildIterator() {
50 return _children.iterator();
51 }
52 public jq_Class getClas() {
53 return _class;
54 }
55 public void reset() {
56 this._parent = null;
57 _children = new HashSet();
58 }
59 public void setRoot(ClassHieraryNode n) {
60
61 this._parent = n;
62 n.addChild(this);
63 }
64 public String toLongString() {
65 return _class.getJDKDesc();
66 }
67 public String toString(){
68 return _class.toString();
69 }
70 public List getChilden() {
71 return Arrays.asList(_children.toArray());
72 }
73 }
74 Set _nodes = new HashSet();
75 ClassHieraryNode _root = null;
76
77 ClassHierarchy(ClassHieraryNode root){
78 this._root = root;
79 add(_root);
80 }
81
82 ClassHierarchy(jq_Class root){
83 this._root = new ClassHieraryNode(root);
84 add(_root);
85 }
86
87 public ClassHierarchy(jq_Class root, Collection c) {
88 this._root = new ClassHieraryNode(root);
89 Assert._assert(_root != null);
90
91 add(_root);
92
93 for(Iterator iter = c.iterator(); iter.hasNext();) {
94 jq_Class c2 = (jq_Class)iter.next();
95
96 add(c2);
97 }
98 }
99
100 private void add(ClassHieraryNode node) {
101 _nodes.add(node);
102 }
103
104 void add(jq_Class c) {
105 if(!hasClass(c)) {
106 _nodes.add(new ClassHieraryNode(c));
107 }
108 }
109
110 private ClassHieraryNode getClassNode(jq_Class c) {
111
112 for(Iterator iter = _nodes.iterator(); iter.hasNext();) {
113 ClassHieraryNode node = (ClassHieraryNode)iter.next();
114
115 if(node.getClas() == c) {
116 return node;
117 }
118 }
119
120 return null;
121 }
122
123 boolean hasClass(jq_Class c) {
124 return getClassNode(c) != null;
125 }
126
127 public void makeHierarchy() {
128 if(_nodes.size() <= 1) return;
129 Assert._assert(_root != null, "Root is not set in the beginning of makeHierarchy");
130
131 resetNodes();
132
133 for(Iterator iter = _nodes.iterator(); iter.hasNext();) {
134 ClassHieraryNode node = (ClassHieraryNode)iter.next();
135 jq_Class c = node.getClas();
136
137 do {
138 if(c instanceof jq_Class && ((jq_Class)c).isInterface()){
139
140 }
141
142 if(c.getDeclaredInterface(_root.getClas().getDesc()) != null){
143
144
145 if(node != _root){
146 node.setRoot(_root);
147 Assert._assert(_root.getChildCount() > 0);
148 }
149 break;
150 }
151 jq_Class superClass = (jq_Class)c.getSuperclass();
152 ClassHieraryNode n = getClassNode(superClass);
153 if(n != null) {
154
155 node.setRoot(n);
156 }
157 if(superClass == c){
158 break;
159 }
160 c = superClass;
161 } while(c != null);
162 }
163 Assert._assert(_root != null, "Root is not set at the end of makeHierarchy");
164 Assert._assert(_root.getChildCount() > 0, "Root is not connected to any children");
165 }
166
167 public void printHierarchy() {
168 if(size() <= 0) return;
169 Assert._assert(_root != null);
170
171 System.out.println("Printing a hierarchy of size " + size() + " rooted at " + _root);
172 printHierarchyAux(_root, "");
173 }
174
175 private int size() {
176 return _nodes.size() - 1;
177 }
178
179 /***
180 * Compares class names.
181 * */
182 public class ClassComparator implements Comparator {
183 public int compare(Object arg0, Object arg1) {
184 return arg0.toString().toLowerCase().compareTo(arg1.toString().toLowerCase());
185 }
186 }
187
188 private void printHierarchyAux(ClassHieraryNode node, String string) {
189 System.out.print(string + node.toString());
190 System.out.println(node.getChildCount() == 0 ? "" : (" " + node.getChildCount()));
191 List children = node.getChilden();
192 Comparator comparator = new ClassComparator();
193 Collections.sort(children, comparator);
194 for(Iterator iter = children.iterator(); iter.hasNext();) {
195 ClassHieraryNode child = (ClassHieraryNode)iter.next();
196
197 Assert._assert(child != node, "Child: " + child + " is the same as " + node);
198 printHierarchyAux(child, string + "\t");
199 }
200 }
201
202 private void resetNodes() {
203 Assert._assert(_root != null, "Root is not set in the beginning of resetNodes");
204 for(Iterator iter = _nodes.iterator(); iter.hasNext();) {
205 ClassHieraryNode node = (ClassHieraryNode)iter.next();
206 node.reset();
207 }
208 Assert._assert(_root != null, "Root is not set at the end of resetNodes");
209 }
210 }
211
212 /***
213 * Represents the fact that
214 * this.method() <= source1.method() + source2.method()...
215 * */
216 class ResultCorrelation {
217
218 jq_Class _this;
219 jq_Field _that;
220
221 ResultCorrelation(jq_Class c){
222 this._this = c;
223
224 }
225 void addSource(jq_Field field) {
226
227 _that = field;
228 }
229 int getSourceCount() {
230
231 return 1;
232 }
233 public String toString() {
234 return "<Correlation: " + _this + " ~ " + _that.getType() + ">";
235 }
236 public jq_Class getThis() {
237 return _this;
238 }
239 public jq_Field getThat() {
240 return _that;
241 }
242 }
243
244 public class FindCollectionImplementations {
245 private static CallGraph _cg;
246
247 static jq_Class _collectionClass = null;
248 static jq_Class _iteratorClass = null;
249 static jq_Class _setClass = null;
250 static jq_Class _mapClass = null;
251 static jq_Class _enumerationClass = null;
252
253 static final boolean FILTER_LOCAL = false;
254
255
256 static final String COLLECTION_SIGNATURE = "Ljava.util.Collection;";
257 static final String SET_SIGNATURE = "Ljava.util.Set;";
258 static final String MAP_SIGNATURE = "Ljava.util.Map;";
259 static final String ENUMERATION_SIGNATURE= "Ljava.util.Enumeration;";
260 static final String ITERATOR_SIGNATURE = "Ljava.util.Iterator;";
261
262 public static void main(String[] args) {
263 HostedVM.initialize();
264 initPredefinedClasses();
265 ClassAndMethod.initializeClasses();
266
267 Iterator i = null;
268 for (int x=0; x<args.length; ++x) {
269 if (args[x].equals("-file")) {
270 try {
271 BufferedReader br = new BufferedReader(new FileReader(args[++x]));
272 LinkedList list = new LinkedList();
273 for (;;) {
274 String s = br.readLine();
275 if (s == null) break;
276 if (s.length() == 0) continue;
277 if (s.startsWith("%")) continue;
278 if (s.startsWith("#")) continue;
279 list.add(s);
280 }
281 i = new AppendIterator(list.iterator(), i);
282 }catch(IOException e) {
283 e.printStackTrace();
284 System.exit(2);
285 }
286
287 } else
288 if (args[x].endsWith("*")) {
289 i = new AppendIterator(PrimordialClassLoader.loader.listPackage(args[x].substring(0, args[x].length()-1)), i);
290 } else
291 if(args[x].charAt(0) == '-'){
292 System.exit(2);
293 }else {
294 String classname = args[x];
295 i = new AppendIterator(Collections.singleton(classname).iterator(), i);
296 }
297 }
298
299 FindCollectionImplementations finder = new FindCollectionImplementations(i);
300 finder.run(true);
301 }
302 private Set _classes;
303 private Set _collections;
304 private Set _iterators;
305 private Set _sets;
306 private Set _maps;
307 private Set _enumerations;
308
309 public FindCollectionImplementations(Iterator i) {
310 Collection roots = new LinkedList();
311 Collection root_classes = new LinkedList();
312 while(i.hasNext()) {
313 jq_Class c = (jq_Class) jq_Type.parseType((String)i.next());
314 c.load();
315 root_classes.add(c);
316
317 roots.addAll(Arrays.asList(c.getDeclaredStaticMethods()));
318 }
319
320
321 System.out.println("Roots: " + roots);
322
323 System.out.print("Building call graph...");
324 long time = System.currentTimeMillis();
325 _cg = new RootedCHACallGraph();
326 _cg.setRoots(roots);
327
328
329 time = System.currentTimeMillis() - time;
330 System.out.println("done. ("+(time/1000.)+" seconds)");
331 _classes = getClasses(_cg.getAllMethods());
332 if(FILTER_LOCAL) _classes = filter(_classes, root_classes);
333
334 if(FILTER_LOCAL){
335 System.out.println("Considering classes: " + _classes);
336 }
337
338 _collections = new HashSet();
339 _iterators = new HashSet();
340 _sets = new HashSet();
341 _maps = new HashSet();
342 _enumerations = new HashSet();
343
344
345 initPredefinedClasses();
346
347 Assert._assert(_collectionClass != null);
348 Assert._assert(_iteratorClass != null);
349 Assert._assert(_setClass != null);
350 }
351
352 static void initPredefinedClasses() {
353 _collectionClass = (jq_Class)jq_Type.parseType(COLLECTION_SIGNATURE);
354 _iteratorClass = (jq_Class)jq_Type.parseType(ITERATOR_SIGNATURE);
355 _setClass = (jq_Class)jq_Type.parseType(SET_SIGNATURE);
356 _mapClass = (jq_Class)jq_Type.parseType(MAP_SIGNATURE);
357 _enumerationClass = (jq_Class)jq_Type.parseType(ENUMERATION_SIGNATURE);
358
359 _collectionClass.prepare();
360 _iteratorClass.prepare();
361 _setClass.prepare();
362 _mapClass.prepare();
363 _enumerationClass.prepare();
364 }
365
366 private Set filter(Set classes, Collection roots) {
367 Set prefixes = new HashSet();
368 for(Iterator iter = roots.iterator(); iter.hasNext();) {
369 jq_Class root = (jq_Class)iter.next();
370 StringTokenizer t = new StringTokenizer(root.getJDKDesc(), ".");
371 String prefix = t.nextToken();
372 prefixes.add(prefix);
373 }
374 System.out.println("Recognized prefixes: " + prefixes);
375
376 Set result = new HashSet();
377 for(Iterator iter = classes.iterator(); iter.hasNext();) {
378 jq_Class c = (jq_Class)iter.next();
379 StringTokenizer t = new StringTokenizer(c.getJDKDesc(), ".");
380 String prefix = t.nextToken();
381
382 if(prefixes.contains(prefix)) {
383 result.add(c);
384 }
385 }
386
387 return result;
388 }
389
390 private void findCollections() {
391 for(Iterator iter = _classes.iterator(); iter.hasNext(); ) {
392 jq_Class c = (jq_Class)iter.next();
393
394 if(
395 c.getDeclaredInterface(_collectionClass.getDesc()) != null &&
396 c.getDeclaredInterface(c.getDesc()) == null)
397 {
398 _collections.add(c);
399 }
400 }
401 }
402 private void findIterators() {
403 for(Iterator iter = _classes.iterator(); iter.hasNext(); ) {
404 jq_Class c = (jq_Class)iter.next();
405
406 if(c.getDeclaredInterface(_iteratorClass.getDesc()) != null) {
407 _iterators.add(c);
408 }
409 }
410 }
411 private void findSets() {
412 for(Iterator iter = _classes.iterator(); iter.hasNext(); ) {
413 jq_Class c = (jq_Class)iter.next();
414
415 if(c.getDeclaredInterface(_setClass.getDesc()) != null) {
416 _sets.add(c);
417 }
418 }
419 }
420 private void findMaps() {
421 for(Iterator iter = _classes.iterator(); iter.hasNext(); ) {
422 jq_Class c = (jq_Class)iter.next();
423
424 if(c.getDeclaredInterface(_mapClass.getDesc()) != null) {
425 _maps.add(c);
426 }
427 }
428 }
429 private void findEnumerations() {
430 for(Iterator iter = _classes.iterator(); iter.hasNext(); ) {
431 jq_Class c = (jq_Class)iter.next();
432
433 if(c.getDeclaredInterface(_enumerationClass.getDesc()) != null) {
434 _enumerations.add(c);
435 }
436 }
437 }
438
439 private Set getClasses(Collection collection) {
440 HashSet result = new HashSet();
441 for(Iterator iter = collection.iterator(); iter.hasNext(); ) {
442 jq_Method method = (jq_Method)iter.next();
443
444
445 jq_Class c = method.getDeclaringClass();
446 if(c != null) {
447 result.add(c);
448 }
449 }
450
451 return result;
452 }
453
454 private void printCollection(Collection collection) {
455 Iterator iter = collection.iterator();
456 while(iter.hasNext()) {
457 jq_Class c = (jq_Class)iter.next();
458
459 System.out.println("\t" + c);
460 }
461 }
462
463 private void reportStats(boolean verbose) {
464 if(verbose) {
465 System.out.println("Found " + _collections.size() + " collections:");
466
467 ClassHierarchy h = new ClassHierarchy(_collectionClass, _collections);
468 h.makeHierarchy();
469 h.printHierarchy();
470
471 System.out.println("Found " + _sets.size() + " sets");
472
473 h = new ClassHierarchy(_setClass, _sets);
474 h.makeHierarchy();
475 h.printHierarchy();
476
477 System.out.println("Found " + _maps.size() + " maps");
478
479 h = new ClassHierarchy(_mapClass, _maps);
480 h.makeHierarchy();
481 h.printHierarchy();
482
483 System.out.println("Found " + _enumerations.size() + " enumerations");
484
485 h = new ClassHierarchy(_enumerationClass, _enumerations);
486 h.makeHierarchy();
487 h.printHierarchy();
488
489 System.out.println("Found " + _iterators.size() + " iterators");
490
491 h = new ClassHierarchy(_iteratorClass, _iterators);
492 h.makeHierarchy();
493 h.printHierarchy();
494 }
495
496 System.out.println("Found " +
497 _collections.size() + " collections, " +
498 _sets.size() + " sets, " +
499 _maps.size() + " maps, " +
500 _maps.size() + " enumerations, " +
501 _iterators.size() + " iterators "
502 );
503 }
504
505 protected void run(boolean verbose){
506
507
508
509 findCollections();
510 findSets();
511 findMaps();
512 findEnumerations();
513 findIterators();
514 if(verbose) {
515 final String LINE = repeat("-", 100);
516
517 System.out.println(LINE);
518 System.out.println("Collections:");
519 findReachable(_collections);
520
521 System.out.println(LINE);
522 System.out.println("Sets:");
523 findReachable(_sets);
524
525 System.out.println(LINE);
526 System.out.println("Maps:");
527 findReachable(_maps);
528
529 System.out.println(LINE);
530 System.out.println("Enumerations:");
531 findReachable(_enumerations);
532
533 System.out.println(LINE);
534 System.out.println("Iterators:");
535 findReachable(_iterators);
536 System.out.println(LINE);
537 }
538
539 findCorrelations(_iterators);
540
541 reportStats(verbose);
542 }
543
544 static class ClassAndMethod {
545 jq_Class _c;
546
547 String _methodName;
548 static Map
549
550 ClassAndMethod(jq_Class c, String m){
551 this._c = c;
552 this._methodName = m;
553 }
554
555 static void initializeClasses(){
556 if(_data != null) return;
557 _data = new HashMap();
558
559 _data.put(_iteratorClass, new ClassAndMethod(_iteratorClass, "next") );
560 _data.put(_collectionClass, new ClassAndMethod(_collectionClass, "iterator") );
561 _data.put(_enumerationClass, new ClassAndMethod(_enumerationClass, "nextElement") );
562 _data.put(_setClass, new ClassAndMethod(_setClass, "iterator") );
563 _data.put(_mapClass, new ClassAndMethod(_mapClass, "get") );
564
565 System.out.println("Initialized information about " + _data.size() + " classes");
566 }
567
568 public static ClassAndMethod retriveClassAndMethod(jq_Class c) {
569 return (ClassAndMethod)_data.get(c);
570 }
571
572 public String getMethodName() {
573 return _methodName;
574 }
575 }
576
577 private void findCorrelations(Set collections) {
578 for(Iterator iter = collections.iterator(); iter.hasNext();) {
579 jq_Class c = (jq_Class)iter.next();
580 jq_Field[] fields = c.getDeclaredInstanceFields();
581 Collection eligibleFields = new LinkedList();
582
583
584 for(int i = 0; i < fields.length; i++) {
585 jq_Field field = fields[i];
586 jq_Type type = field.getType();
587 if(!type.isClassType()) continue;
588 if(!isStandardClass((jq_Class)type)) continue;
589
590 eligibleFields.add(field);
591 }
592
593 if(eligibleFields.size() == 1) {
594 jq_Field that = (jq_Field)eligibleFields.iterator().next();
595
596
597
598 ResultCorrelation r = new ResultCorrelation(c);
599 r.addSource(that);
600
601
602 System.out.println("Considering " + r);
603
604 try {
605 tryToProve(r);
606 }catch(ClassCastException e) {
607
608 }catch(RuntimeException e) {
609
610 }
611 }
612 }
613 }
614
615 private boolean isStandardClass(jq_Class c) {
616 return getStandardClass(c) != null;
617 }
618
619 /***
620 Prove the correlation between the results.
621 */
622 private void tryToProve(ResultCorrelation r) {
623 jq_Class thisClass = r.getThis();
624 jq_Class thatClass = (jq_Class)r.getThat().getType();
625
626 ClassAndMethod thisCAM = getClassAndMethod(thisClass);
627 ClassAndMethod thatCAM = getClassAndMethod(thatClass);
628
629 jq_Method thisMethod = thisClass.getDeclaredMethod(thisCAM.getMethodName());
630 jq_Method thatMethod = thatClass.getDeclaredMethod(thatCAM.getMethodName());
631
632 if(thisMethod == null) throw new RuntimeException("Can't find the method " + thisCAM.getMethodName() + " in " + thisClass + ": " + thisClass.getMembers());
633 if(thatMethod == null) throw new RuntimeException("Can't find the method " + thatCAM.getMethodName() + " in " + thatClass + ": " + thatClass.getMembers());
634
635 System.out.println("\t" + "Comparing the result of " + thisMethod + " and " + thatMethod);
636
637
638 Set thisNodeReturns = MethodSummary.getSummary(thisMethod).getReturned();
639 if(thisNodeReturns.size() != 1) {
640 throw new RuntimeException("There are " + thisNodeReturns.size() + " nodes for " + thisMethod);
641 }
642 ReturnedNode thisNodeReturn = (ReturnedNode)thisNodeReturns.iterator().next();
643 System.out.println("thisNodeReturn: " + thisNodeReturns);
644
645
646 Set thatNodeReturns = MethodSummary.getSummary(thatMethod).getReturned();
647 System.out.println("thatNodeReturns: " + thatNodeReturns);
648 if(thatNodeReturns.size() != 1) {
649 throw new RuntimeException("There are " + thatNodeReturns.size() + " nodes for " + thatMethod);
650 }
651
652 ReturnedNode thatNodeReturn = (ReturnedNode)thatNodeReturns.iterator().next();
653 System.out.println("thatNodeReturn: " + thatNodeReturn);
654
655
656
657 }
658
659 protected ClassAndMethod getClassAndMethod(jq_Class classType) {
660 jq_Class stdClassThat = getStandardClass(classType);
661 Assert._assert(stdClassThat != null, "Unexpected class " + classType);
662 ClassAndMethod cam = ClassAndMethod.retriveClassAndMethod(stdClassThat);
663 Assert._assert(cam != null, "Can't find a method for " + stdClassThat);
664
665 return cam;
666 }
667
668 private jq_Class getStandardClass(jq_Class c) {
669 Assert._assert(_setClass.isPrepared() && _collectionClass.isPrepared() && _mapClass.isPrepared());
670 c.prepare();
671
672 if(c.implementsInterface(_setClass) || c == _setClass) {
673 return _setClass;
674 } else {
675 if(c.implementsInterface(_collectionClass) || c == _collectionClass) {
676 return _collectionClass;
677 }
678 }
679 if(c.implementsInterface(_iteratorClass) || c == _iteratorClass) {
680 return _iteratorClass;
681 }else
682 if(c.implementsInterface(_mapClass) || c == _mapClass) {
683 return _mapClass;
684 }else
685 if(c.implementsInterface(_enumerationClass) || c == _enumerationClass) {
686 return _enumerationClass;
687 }
688
689 return null;
690 }
691
692 private void findReachable(Set classes) {
693 for(Iterator iter = classes.iterator(); iter.hasNext();) {
694 jq_Class c = (jq_Class)iter.next();
695
696 Collection reachable = findReachable(c);
697 if(!reachable.isEmpty()) {
698 System.out.println(cutto(c.toString(), 40) + ": [");
699 for(Iterator iter2 = reachable.iterator(); iter2.hasNext();) {
700 Object o = iter2.next();
701 if(o instanceof jq_Field) {
702 jq_Field field = (jq_Field)o;
703 jq_Type type = field.getType();
704
705 if(type.isClassType()) {
706 System.out.println(repeat(" ", 40) + "\t" +
707 cutto(field.getName().toString(), 30) +
708 " : " + type + typeSig(type));
709 }
710 } else {
711 System.out.println(repeat(" ", 40) + "\t" + o + " ");
712 }
713 }
714 System.out.println(repeat(" ", 40) + "]");
715 } else {
716 System.out.println(cutto(c.toString(), 40) + ": []");
717 }
718 }
719 }
720
721 private String typeSig(jq_Type type) {
722 if(!(type instanceof jq_Class)) return "";
723 StringBuffer buf = new StringBuffer();
724 jq_Class c = (jq_Class)type;
725
726 if(c.implementsInterface(_setClass) || c == _setClass) {
727 buf.append(" [Set]");
728 } else {
729 if(c.implementsInterface(_collectionClass) || c == _collectionClass) {
730 buf.append(" [Collection]");
731 }
732 }
733 if(c.implementsInterface(_iteratorClass) || c == _iteratorClass) {
734 buf.append(" [Iterator]");
735 }else
736 if(c.implementsInterface(_mapClass) || c == _mapClass) {
737 buf.append(" [Map]");
738 }else
739 if(c.implementsInterface(_enumerationClass) || c == _enumerationClass) {
740 buf.append(" [Enumeration]");
741 }
742
743 return buf.toString();
744 }
745
746 private Collection findReachable(jq_Class c) {
747 Collection result = new LinkedList();
748
749 result.addAll(Arrays.asList(c.getDeclaredInstanceFields()));
750
751 return result;
752 }
753
754 private static String cutto(String string, int to) {
755 return string.length() < to ?
756 string + repeat(" ", to - string.length()) :
757 string.substring(0, to - 3) + "...";
758 }
759 private static String repeat(String string, int to) {
760 StringBuffer result = new StringBuffer();
761 for(int i = 0; i < to; i++) {
762 result.append(string);
763 }
764
765 return result.toString();
766 }
767 }